﻿/*
    Copyright 2010, 2011 Eric Wong
	contact@optimalcycling.com
	http://www.optimalcycling.com
	Optimal Cycling - Advanced power pacing program for cyclists
	
	This file is part of Optimal Cycling.

    Optimal Cycling is free software: you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    Optimal Cycling is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public License
    along with Optimal Cycling.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef _FILE_SORT_H_
#define _FILE_SORT_H_

#ifndef __OPENCL_VERSION__
	#include "Options.h"
	#include "Constants.h"
#endif

// Based on code from http://jeffreystedfast.blogspot.com/2007/03/quick-sort.html
// MIT License
// NOTE: THIS IMPLEMENTATION ONLY WORKS FOR POSITIVE NUMBERS!

// Alternative quicksort in PHP: http://www.algorithmist.com/index.php/Quicksort_non-recursive.php
// Alternative quicksort parallelized: http://www.codeproject.com/KB/threads/Parallel_Quicksort.aspx
// Parallelized quicksort in C#: http://www.codeproject.com/KB/threads/tricky_multicore.aspx

typedef struct {
    sizeT lo;
    sizeT hi;
} qstack_t;

inline void
SwapEx(__global real* fitness, __global sizeT* correspondingIndex, const sizeT lo, const sizeT hi)
{
	real fitnessTemp;
	sizeT correspondingIndexTemp;

    fitnessTemp = fitness[lo];
    fitness[lo] = fitness[hi];
    fitness[hi] = fitnessTemp;

    correspondingIndexTemp = correspondingIndex[lo];
    correspondingIndex[lo] = correspondingIndex[hi];
    correspondingIndex[hi] = correspondingIndexTemp;
}

inline void
QuickSortEx (__global real* fitness, __global sizeT* correspondingIndex, const sizeT n)
{
    qstack_t stack[QUICKSORT_STACK_SIZE], *sp;
    sizeT lo, hi;
    sizeT low, high;
    real pivot;

    if (n < 2)
        return;

    /* push our initial values onto the stack */
    sp = stack;
    sp->lo = 0;
    sp->hi = n;
    sp++;

    while (sp > stack) {
        /* pop lo and hi off the stack */
        sp--;
        high = sp->hi;
        low = sp->lo;

        hi = high - 1;
        lo = low;

        pivot = fitness[lo];

        while (1) {
            while (lo < high && fitness[lo] < pivot)
                lo++;

            while (hi > low && fitness[hi] >= pivot)
                hi--;

            if (lo < hi) {
                /* swap */
				SwapEx(fitness, correspondingIndex, lo, hi);
                hi--;
            } else {
                hi++;

                if (hi == high) {
                    /* done with this segment */
                    break;
                }

                /* push the larger segment onto the
                 * stack and continue sorting the
                 * smaller segment. */
                if ((hi - low) > (high - hi)) {
                    sp->lo = low;
                    sp->hi = hi;
                    sp++;

                    hi = high;
                    low = lo;
                } else {
                    sp->hi = high;
                    sp->lo = hi;
                    sp++;

                    high = hi;
                    lo = low;
                }

                pivot = fitness[lo];
                hi--;
            }
        }
    }
}

#endif		// _FILE_SORT_H_
